#include "KamaCoder.h"
using namespace std;

// 构建并查集代码
// 初始化并查集
void KamaCoder109::init(int n) {
  for (int i = 1; i <= n; i++) {
    father[i] = i;
  }
}
// 找到根节点

int KamaCoder109::find(int x) {
  if (father[x] != x) {
    father[x] = find(father[x]);  // 路径压缩
  }
  return father[x];
}

// 判断两个节点是都在一个并集中
bool KamaCoder109::isSame(int x, int y) {
  x = find(x);
  y = find(y);
  return x == y;
}
// 将两个节点合并到一个并集中
void KamaCoder109::join(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;  // 已经在一个并集中
  father[x] = y;       // 合并并查集
}

// 判断删除指定边后能否形成树
bool KamaCoder109::isTreeAfterRemoveEdge(vector<vector<int>>& edges,
                                         int index) {
  // 初始化并查集
  init(m_n);
  // 遍历所有边，将边加入并查集
  for (int i = 0; i < m_n; i++) {
    if (i == index) continue;  // 依据删除的边的下标，跳过
    if (isSame(edges[i][0], edges[i][1])) return false;  // 存在环,一定不是树
    join(edges[i][0], edges[i][1]);
  }
  // 遍历完所有边，没有环，是树
  return true;  // 无环，是树
}

// 找到构成环的边
void KamaCoder109::getRmoveEdge(vector<vector<int>>& edges) {
  // 初始化并查集
  init(m_n);
  // 遍历所有边，将边加入并查集
  for (int i = 0; i < m_n; i++) {
    if (isSame(edges[i][0], edges[i][1])) {  // 存在环
      cout << edges[i][0] << " " << edges[i][1] << endl;
      return;  // 输出结果
    }
    join(edges[i][0], edges[i][1]);
  }
  return;
}

// 主函数，用于处理输入和输出结果
int KamaCoder109::run() {
  // 输入数据
  int s, t;
  vector<vector<int>> edges;  //
  cin >> m_n;
  // 记录每个节点的入度情况
  vector<int> indegree(m_n + 1, 0);
  for (int i = 0; i < m_n; i++) {
    cin >> s >> t;
    indegree[t]++;            // 记录每个节点的入度情况
    edges.push_back({s, t});  // 记录所有边
  }
  vector<int> vec;  // 记录入度为2的边的下标
  // 要进行倒序进行查找
  for (int i = m_n - 1; i >= 0; i--) {
    // 从放入边的节点倒序查找入度为2的边
    if (indegree[edges[i][1]] == 2) vec.push_back(i);  // 记录入度为2的边的下标
  }

  if (vec.size() > 0) {
    // 判断删除的边是否形成树,如果包含多个入度为2的边，优先删除第一个放入的，即vec[0]
    if (isTreeAfterRemoveEdge(edges, vec[0])) {
      // 输出结果
      cout << edges[vec[0]][0] << " " << edges[vec[0]][1] << endl;
    } else {  // 否则删除倒数第二个，入度为2的边必然有两条边
      cout << edges[vec[1]][0] << " " << edges[vec[1]][1] << endl;
    }
    return 0;
  }

  // 没有remove掉的边，则是第三种情况
  // 一定是有有向环的，找到构成环的边返回即可
  getRmoveEdge(edges);

  return 0;
}